# -*- coding: utf-8 -*-
"""
Created on Tue Nov 13 23:01:23 2018

@author: Administrator
"""

class DoubleLinkedNode:
    """双链表节点
    """
    def __init__(self, element, prev = None, next_ = None):
        self.element = element
        self.prev = prev
        self.next = next_
        
#node = DoubleLinkedNode(5)
#print(node.element)
#print(node.prev)

class DoubleLinkedList:
    """双链表
    能够实现O(1)的首尾端添加/删除
    """
    def __init__(self):
        """初始化双链表
        结构为带头指针、尾指针、length的双链表
        """
        self.head = None
        self.rear = None
        self.length = 0
    
    def is_empty(self):
        if self.head is None and self.rear is None:
            return True
        return False
    
    def prepend(self, element):
        """表头添加元素
        """
        node = DoubleLinkedNode(element)
        if self.head is None and self.rear is None:
            self.head = node
            self.rear = node
        else:
            node.next = self.head # 新元素指向表头
            self.head.prev = node # 表头prev指向新元素
            self.head = node      # 头指针指向新元素
        self.length += 1
        
    def append(self, element):
        """表尾添加元素
        """
        node = DoubleLinkedNode(element)
        if self.head is None and self.rear is None:
            self.head = node
            self.rear = node
        else:
            self.rear.next = node # 表尾next指向新元素
            node.prev = self.rear # 新元素的prev指向表尾
            self.rear = node      # 表尾指针指向新元素
        self.length += 1
        
    def delete_first(self):
        """删除表头元素
        返回首元素
        """
        if self.head is None and self.rear is None:
            raise ValueError("double linked list is empty!")
        e = self.head
        if self.head.next is None:
            self.head = None
            self.rear = None
        else:
            self.head = self.head.next
            e.next = None # 清空 删除元素e的指针域
        self.length -= 1
        return e
        
    def delete_last(self):
        """删除表尾元素
        返回尾元素
        """
        if self.head is None and self.rear is None:
            raise ValueError("double linked list is empty!")
        e = self.rear
        if self.head.next is None:
            self.head = None
            self.rear = None
        else:
            self.rear = self.rear.prev
            e.prev = None
        self.length -= 1
        return e
        
    def delete(self, element):
        """删除表中任意元素
        """
        # 遍历到element元素位置
        p = self.head
        while p is not None:
            # 如果为表首元素
            if p.prev is None and p.element == element:
                self.delete_first()
                return True
            # 如果为表尾元素
            if p.next is None and p.element == element:
                self.delete_last()
                return True
            # 如果为表中间元素
            if p.element == element:
                p.prev.next = p.next
                p.next.prev = p.prev
                return True

            p = p.next
        return False
        
    def print_all(self):
        result = []
        p = self.head
        while p is not None:
            result.append(p.element)
            p = p.next
        return result
    
        
